package a4;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
import org.jgrapht.graph.WeightedMultigraph;

/**
 * Algorithmus von Hierholzer
 */
public class Hierholzer {
	public List<String> GetEulerCircle(WeightedMultigraph<String, DefaultWeightedEdge> graph) {
		Set<DefaultWeightedEdge> globalVisited = new HashSet<>();
		List<List<String>> circles = new ArrayList<>();
		
		List<String> vertexes = new ArrayList<>(graph.vertexSet());
		String start = vertexes.get(0);
		String current;
		
		while(!globalVisited.equals(graph.edgeSet())) { //Solange nicht alle Kanten abgelaufen sind
			if (!circles.isEmpty()) {
				for (List<String> circle : circles) {
					for(String vertex : circle) {
						if (!globalVisited.containsAll(graph.edgesOf(vertex))) {
							start = vertex;
							break;
						}
					}
				}
			}			
			
			List<String> circle = new ArrayList<>();
			current = start;
			do {
				circle.add(current);
				for(DefaultWeightedEdge e : graph.edgesOf(current)) {
					if (!globalVisited.contains(e)) {
						globalVisited.add(e);
						current = (!graph.getEdgeTarget(e).equals(current)) ? graph.getEdgeTarget(e) : graph.getEdgeSource(e);
						break;
					}
				}

			} while (!current.equals(start));
			circle.add(start);
			circles.add(circle);		
		}
		
		List<String> resultCircle = new ArrayList<>();
		Set<List<String>> visitedCircles = new HashSet<>();
		Stack<List<String>> circleStack = new Stack<>();
		circleStack.push(circles.get(0));
		resultCircle.add(circleStack.peek().get(0));
		circleStack.peek().remove(0);
		visitedCircles.add(circleStack.peek());
		
		while (!circleStack.isEmpty()) {
			List<String> currentCircle = circleStack.peek();
			if (currentCircle.isEmpty()) {
				circleStack.pop();
				continue;
			}				
			String vertex = currentCircle.get(0);
			if (vertex.equals("9")) {
				int c = 1 +2;
			}				
			resultCircle.add(vertex);
			currentCircle.remove(0);
			for(List<String> circ : circles) {
				if (circ.contains(vertex) && !safeSetContains(visitedCircles, circ)) {
					visitedCircles.add(circ);
					circleStack.push(circ);
					circ.remove(0);					
					break;
				}				
			}
			
		}
		System.out.println(resultCircle);
		return resultCircle;
	}
	
	private <T> boolean safeSetContains (Set<T> set, T obj) {
		for(T t : set) {
			if (obj == t)
				return true;			
		}
		return false;
	}
	
	
}
